package q2155_maxScoreIndices;

import java.util.ArrayList;
import java.util.List;

/*
如果要遍历一次就解决 则需要一定的数学敏感
首先列出左右两边 0的和通式 和 1的和通式
两者相加并转换 可以转化为求0 - n-1 这段 1 - 2*nums[i]的最大和
这个最大和的特征也就是遇到0 则加1 遇到1 则减1
 */
public class Solution_2 {
    public List<Integer> maxScoreIndices(int[] nums) {
        List<Integer> ans = new ArrayList<>();
        ans.add(0);
        int max = 0, preSum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                preSum++;
                if (preSum > max) {
                    ans = new ArrayList<>();
                    ans.add(i + 1);
                    max = preSum;
                } else if (preSum == max) {
                    ans.add(i + 1);
                }
            } else {
                preSum--;
            }
        }
        return ans;
    }
}
